import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class DeterministicFiniteAutomaton {
	/* defined by a finite set of states, a finite set of input symbols
	 * called the alphabet, a transition function, a start state, and an
	 * accept state
	 */
	ArrayList<State> states;
	Set<Character> alphabet;
	TransitionFunction<Integer,Character,State> transitions;
	State startState;
	Set<State> acceptStates;
	State currentState;
	
	public DeterministicFiniteAutomaton(Set<Character> alphabet) {
		this.alphabet = alphabet;
		this.states = new ArrayList<State>();
		this.acceptStates = new HashSet<State>();
		this.transitions = new TransitionFunction<Integer,Character,State>();
		this.startState = null;
	}
	
	public State doTransition(Character c) {
		currentState = transitions.getResult(currentState.getId(), c);
		return currentState;
	}
	
	public Integer addState(State s) {
		return this.addState(s, false);
	}
	
	public Integer addState(State s, boolean isAccepting) {
		states.add(s);
		int index = states.indexOf(s);
		s.setId(index);
		if (isAccepting) {
			acceptStates.add(s);
		}
		return index;
	}
	
	public void setCurrentState(State s) {
		this.currentState = s;
	}
	
	public void setTransition(State from, Character c, State to) {
		if (!alphabet.contains(c)) {
			// do better error handling, make an exception or something
			System.err.println("symbol " + c + " not in alphabet");
			System.exit(1);
		}
		transitions.setResult(from.getId(), c, to);
	}
	
	/**
	 * THIS METHOD CONSUMES THE CURRENT DFA!
	 * During the minimization process, the current DFA gets messed up pretty
	 * badly. This could be fixed, but it doesn't seem like we'll need the
	 * original DFA after it's been minimized.
	 * @return a minimal DFA
	 */
	public DeterministicFiniteAutomaton minimize() {
		/* distinguish = {<p, q> | p in F and q not in F}
		 * oldDistinguish = nil
		 * while (distinguish not eq oldDistinguish)
		 *  oldDistinguish = distinguish
		 *  for every symbol a and for every <p, q> not in distinguish do
		 *   if <sigma(p, a), sigma(q, a)> in distinguish
		 *    distinguish = distinguish union {<p, q>}
		 */
		int numStates = states.size();
		boolean[][] dist = new boolean[numStates][numStates];
		boolean[][] oldDist = new boolean[numStates][numStates];
		
		// initialize array
		for (int i=0; i<numStates; i++)
			for (int j=0; j<=i; j++) {
				dist[i][j] = false;
			}

		// distinguish final/non-final states
		for (int i=0; i<numStates; i++) {
			for (int j=0; j<i; j++) {
				if (acceptStates.contains(states.get(i)) != acceptStates.contains(states.get(j)))
						dist[i][j] = true;
			}
		}
		
		// loop until two iterations have the same state (i.e. minimized)
		do {
			oldDist = deepCloneArray(dist, numStates);
			
			for (int i=0; i<numStates; i++) {
				State p = states.get(i);
				for (int j=0; j<i; j++) {
					State q = states.get(j);
					if (!dist[i][j])
						for (Character a : alphabet) {
							State sigma1 = transitions.getResult(p.getId(), a);
							State sigma2 = transitions.getResult(q.getId(), a);
							// ensure ordering, we only use half of array
							if (sigma2.getId() > sigma1.getId()) {
								State swap = sigma1;
								sigma1 = sigma2;
								sigma2 = swap;
							}
								
							if (dist[sigma1.getId()][sigma2.getId()])
								dist[i][j] = true;
						}
				}
			}
		} while (!compareArrays(dist, oldDist, numStates));
		
		boolean[] valid = new boolean[numStates];
		for (int i=0; i<numStates; i++) valid[i] = true;
		for (int i=0; i<numStates; i++)
			for (int j=0; j<i; j++)
				if (!dist[i][j]) {
					// run if i and j states are equivalent
					// mark one state invalid
					valid[i] = false;
					
					// track the start state
					if (startState != null && startState.equals(states.get(i)))
						startState = states.get(j);
					
					// update transition references to j in valid states
					for (int k=0; k<numStates; k++)
						if (valid[k])
							for (Character c : alphabet)
								if (transitions.getResult(states.get(k).getId(), c).equals(states.get(i)))
									transitions.setResult(k, c, states.get(j));
				}
		
		// create a new dfa from this information
		DeterministicFiniteAutomaton newDfa = new DeterministicFiniteAutomaton(this.alphabet);
		Map<Integer,Integer> oldToNew = new HashMap<Integer,Integer>();
		// move the states over
		for (int i=0; i<numStates; i++) {
			// only move valid states to new dfa
			if (valid[i]) {
				State s = new State();
				boolean accept = acceptStates.contains(states.get(i));
				int newIndex = newDfa.addState(s, accept);
				// update the map
				oldToNew.put(i, newIndex);
			}
		}
		// move transitions
		TransitionFunction<Integer,Character,State> newTrans = new TransitionFunction<Integer,Character,State>();
		for (int i=0; i<numStates; i++) {
			if (valid[i]) {
				int newIndex = oldToNew.get(i);
				for (Character c : alphabet) {
					State oldTarget = transitions.getResult(states.get(i).getId(), c);
					newTrans.setResult(newIndex, c, newDfa.getState(oldToNew.get(oldTarget.getId())));
				}
			}
		}
		newDfa.setTransitionFunction(newTrans);
		
		// set the start state
		if (startState != null)
			newDfa.setStartState(oldToNew.get(startState.getId()));
		
		return newDfa;
	}
	
	public Integer getNumberOfStates() {
		return this.states.size();
	}
	
	public boolean isInAcceptingState() {
		if (this.currentState == null) return false;
		return acceptStates.contains(this.currentState);
	}
	
	public String toString() {
		String out = "";
		out += "current state: " + currentState + "\n";
		out += "Start state: " + startState + "\n";
		out += "# states: " + states.size() + "\n";
		out += "alphabet:" + "\n";
		for (Character c : alphabet) out += c + " ";
		out += "\n";
		out += "states:" + "\n";
		for (State s : states) {
			if (acceptStates.contains(s)) out += "ACCEPT ";
			out += s + "\n";
		}
		out += "transition table:\n";
		out += transitions.toString();
		return out;
	}
	
	public void setStartState(State s) {
		if (states.contains(s))
			this.setStartState(s.getId());
		else {
			System.err.println("Tried to set start state to a state not in this.states");
			System.exit(1);
		}
	}
	
	public void setStartState(Integer index) {
		this.startState = states.get(index);
		this.currentState = this.startState;
	}
	
	public Set<Character> getAlphabet() {
		return this.alphabet;
	}
	
	public void resetToStartState() {
		this.currentState = this.startState;
	}
	
	protected ArrayList<State> getStates() {
		return this.states;
	}
	
	protected void setTransitionFunction(TransitionFunction<Integer,Character,State> t) {
		this.transitions = t;
	}
	
	protected State getState(int index) {
		return states.get(index);
	}
	
	private static boolean compareArrays(boolean[][] a, boolean[][] b, int length) {
		for (int i=0; i<length; i++)
			for (int j=0; j<i; j++)
				if (a[i][j] != b[i][j])
					return false;
		return true;
	}
	
	private static boolean[][] deepCloneArray(boolean[][] a, int dimension) {
		boolean[][] cloned = new boolean[dimension][];
		for (int i=0; i<dimension; i++) {
			cloned[i] = a[i].clone();
		}
		return cloned;
	}
	
	public static void main(String[] args) {
		Set<Character> alphabet = new HashSet<Character>();
		alphabet.add('0');
		alphabet.add('1');
		DeterministicFiniteAutomaton dfa = new DeterministicFiniteAutomaton(alphabet);

		// test case from slide 14 of:
		// http://www.cs.uiuc.edu/class/fa05/cs475/Lectures/new/lec09.pdf
		State a = new State();
		State b = new State();
		State c = new State();
		State d = new State();
		State e = new State();
		State f = new State();
		State g = new State();
		State h = new State();
		dfa.addState(a);
		dfa.addState(b);
		dfa.addState(c, true);
		dfa.addState(d);
		dfa.addState(e);
		dfa.addState(f);
		dfa.addState(g);
		dfa.addState(h);
		dfa.setStartState(f);
		dfa.setTransition(a, '0', b);
		dfa.setTransition(a, '1', f);
		dfa.setTransition(b, '0', g);
		dfa.setTransition(b, '1', c);
		dfa.setTransition(c, '0', a);
		dfa.setTransition(c, '1', c);
		dfa.setTransition(d, '0', c);
		dfa.setTransition(d, '1', g);
		dfa.setTransition(e, '0', h);
		dfa.setTransition(e, '1', f);
		dfa.setTransition(f, '0', c);
		dfa.setTransition(f, '1', g);
		dfa.setTransition(g, '0', g);
		dfa.setTransition(g, '1', e);
		dfa.setTransition(h, '0', g);
		dfa.setTransition(h, '1', c);

		DeterministicFiniteAutomaton minDfa = dfa.minimize();
		System.out.println(minDfa);

		dfa = new DeterministicFiniteAutomaton(alphabet);

		// test case for start state minimization 
		a = new State();
		b = new State();
		dfa.addState(a);
		dfa.addState(b, true);
		dfa.setTransition(a, '0', b);
		dfa.setTransition(a, '1', b);
		dfa.setTransition(b, '0', b);
		dfa.setTransition(b, '1', b);

		minDfa = dfa.minimize();
		System.out.println(minDfa);
	}
}
